// InsertionSort20211017.cpp

#include <vector>
#include <iostream>

using namespace std;

// 从右手往左手抓扑克牌
// {8, 5, 2, 9, 6, 3}
//        ^右手
// {8, 5}
//     j
// {2, 3, 5, 6, 8, 9} 左手

void insertionSort(vector<int> &array) {
  // 右手的移动位置 从 1 开始一直到 array.size() - 1
  for (int i = 1; i <= (array.size() - 1); ++i) {
    // j 表示插入的位置
    int j = i;

    while (array[j - 1] > array[j] && j > 0) {
      swap(array[j - 1], array[j]);
      --j;
    }
  }
}

int main(int argc, char const *argv[])
{
  /* code */
  vector<int> v{8, 5, 2, 9, 6, 3};

  insertionSort(v);

  for (int n : v) {
    cout<<n<<" ";
  }

  cout<<endl;
  return 0;
}
